package com.lw.leetcode.back.b;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * LCP 56. 信物传送
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/9 16:28
 */
public class ConveyorBelt {

    private String[] matrix;
    private int[][] arr;
    private int m;
    private int n;
    private int t1;
    private int t2;
    List<Integer> list1 = new ArrayList<>();
    List<Integer> list2 = new ArrayList<>();

    public int conveyorBelt(String[] matrix, int[] start, int[] end) {
        if (start[0] == end[0] && start[1] == end[1]) {
            return 0;
        }
        this.matrix = matrix;
        this.m = matrix.length;
        this.n = matrix[0].length();
        arr = new int[m][n];
        this.t1 = end[0];
        this.t2 = end[1];
        list2.add((start[0] << 12) + start[1]);
        for (int[] ints : arr) {
            Arrays.fill(ints, -1);
        }
        find(start[0], start[1], 0);
        if (arr[t1][t2] == 0) {
            return 0;
        }
        while (!list2.isEmpty()) {
            list1.clear();
            list1.addAll(list2);
            list2.clear();
            for (Integer v : list1) {
                int a = v >> 12;
                int b = v & 0XFFF;
                int c = arr[a][b];
                char str = matrix[a].charAt(b);
                if (str == '>') {
                    find(a, b - 1, c + 1);
                    if (arr[t1][t2] > 0) {
                        return arr[t1][t2];
                    }
                    find(a + 1, b, c + 1);
                    if (arr[t1][t2] > 0) {
                        return arr[t1][t2];
                    }
                    find(a - 1, b, c + 1);
                } else if (str == '<') {
                    find(a, b + 1, c + 1);
                    if (arr[t1][t2] > 0) {
                        return arr[t1][t2];
                    }
                    find(a + 1, b, c + 1);
                    if (arr[t1][t2] > 0) {
                        return arr[t1][t2];
                    }
                    find(a - 1, b, c + 1);
                } else if (str == 'v') {
                    find(a, b + 1, c + 1);
                    if (arr[t1][t2] > 0) {
                        return arr[t1][t2];
                    }
                    find(a, b - 1, c + 1);
                    if (arr[t1][t2] > 0) {
                        return arr[t1][t2];
                    }
                    find(a - 1, b, c + 1);
                } else {
                    find(a, b + 1, c + 1);
                    if (arr[t1][t2] > 0) {
                        return arr[t1][t2];
                    }
                    find(a, b - 1, c + 1);
                    if (arr[t1][t2] > 0) {
                        return arr[t1][t2];
                    }
                    find(a + 1, b, c + 1);
                }
            }
            if (arr[t1][t2] > 0) {
                return arr[t1][t2];
            }
        }
        return -1;
    }

    private void find(int a, int b, int c) {
        if (a < 0 || a == m || b < 0 || b == n) {
            return;
        }
        if (a == t1 && b == t2) {
            arr[a][b] = c;
            return;
        }
        if (arr[a][b] == -1 || arr[a][b] > c) {
            arr[a][b] = c;
            list2.add((a << 12) + b);
            char str = matrix[a].charAt(b);
            if (str == '>') {
                find(a, b + 1, c);
            } else if (str == '<') {
                find(a, b - 1, c);
            } else if (str == 'v') {
                find(a + 1, b, c);
            } else {
                find(a - 1, b, c);
            }
        }
    }

}
